package puzzle.projecteuler.p200;

import java.util.Arrays;

import astudy.util.AdvMath;

public class Problem187D {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		int m = 100000000;
		int c = 0;
		Integer[] ps = AdvMath.primes(m);
		for (int i = 0; i < ps.length; i ++) {
			int p = ps[i];
			int qm = (m-1)/p;
			int j = Arrays.binarySearch(ps, qm);
			if (j >= 0) {
			} else {
				j = -j-2;
			}
			if (j >= i) {
				c += (j-i+1);
			}
		}
		System.out.println(c);
	}

}
